#define  _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <stack>
using namespace std;
class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        int ret = 0;
        vector<int> height(n, 0);

        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (mat[i][j] == 0)
                    height[j] = 0;
                else ++height[j];
            }
            ret += func(height);
        }
        return ret;
    }
    int func(const vector<int>& height)
    {
        int count = 0;
        stack<int> st;
        for (int i = 0; i <= height.size(); i++)
        {
            while (!st.empty() && (i == height.size() || height[st.top()] >= height[i]))
            {
                int h = height[st.top()];
                st.pop();
                int w = st.empty() ? i : i - st.top() - 1;
                count += h * w;
            }
            st.push(i);
        }

        return count;
    }
};

int main()
{
    vector<vector<int>> mat = {
        {1,1,1,1,0,1,0},//11
        {1,1,1,0,0,0,1},//13
        {0,1,1,1,1,0,0},//16
        {1,1,0,1,1,0,1},//13
        {1,0,0,0,0,0,1},//4
        {1,1,0,1,1,1,1},//17
        {1,1,0,0,1,1,1}//22
    };

    Solution().numSubmat(mat);
}